package interview.questions.链表中倒数第k个节点;

import interview.questions.从尾到头打印列表.ListNode;

/**
 * 问题：
 * <p>
 * 输入一个链表，输出该链表中倒数第k个结点。
 */
public class Solution {
    /**
     * 解决思路：
     * <p>
     * 两个指针 P1， P2, 先将 P2 向后移 k 个单位，然后 P1， P2 再同时向后移。
     * <p>
     * 注意：
     * 可能会出现 K 大于链表长度的情况， 在 P2 移动的时候进行判断， 如果P2 为空了， 返回空
     *
     */
    public static ListNode FindKthToTail(ListNode head, int k) {
        if (k <= 0) {
            return null;
        }
        ListNode p1 = head;
        ListNode p2 = head;
        for (int i = 0; i < k - 1; i++) {
            // if 中 情况是 k > 链表长度的情况
            if (p1 == null) {
                return null;
            }
            p1 = p1.next;
        }
        if (p1 == null) {
            return null;
        }
        while (p1.next != null) {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p2;
    }
}
